package com.zhang.study.chapter05;

/**
 * 区间和的个数
 * https://leetcode.com/problems/count-of-range-sum/
 */
public class Code01_CountOfRangeSum {

    public static int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = 0;
        long[] preSum = new long[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }

        for (long j : preSum) {
            if (j >= lower && j <= upper) {
                count++;
            }
        }
        int mergeSize = 1;
        while (mergeSize < preSum.length) {
            int left = 0;
            while (left < preSum.length) {
                int mid = left + mergeSize - 1;
                if (mid >= preSum.length) {
                    break;
                }
                int right = Math.min(left + (mergeSize << 1) - 1, preSum.length - 1);

                // 执行计算操作
                int leftIndex = left;
                int rightIndex = left;
                for (int rightCurrent = mid + 1; rightCurrent <= right; rightCurrent++) {
                    long min = preSum[rightCurrent] - upper;
                    long max = preSum[rightCurrent] - lower;
                    while (rightIndex <= mid && preSum[rightIndex] <= max) {
                        rightIndex++;
                    }
                    while (leftIndex <= mid && preSum[leftIndex] < min) {
                        leftIndex++;
                    }
                    count += rightIndex - leftIndex;
                }
                long[] temp = new long[right - left + 1];
                int startIndex = left;
                int midIndex = mid + 1;
                int index = 0;
                while (startIndex <= mid && midIndex <= right) {
                    temp[index++] = preSum[startIndex] <= preSum[midIndex] ? preSum[startIndex++] : preSum[midIndex++];
                }
                while (startIndex <= mid) {
                    temp[index++] = preSum[startIndex++];
                }
                while (midIndex <= right) {
                    temp[index++] = preSum[midIndex++];
                }
                System.arraycopy(temp, 0, preSum, left, temp.length);

                left = right + 1;
            }
            if (mergeSize > preSum.length << 1) {
                break;
            }
            mergeSize <<= 1;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0};
        System.out.println(countRangeSum(nums, 0, 0));
    }


}
